package leetcode.array;

import java.util.Random;

/**
 * @author Cheng Jun Description: 给你一个整数数组 nums，请你将该数组升序排列。
 *     https://leetcode.cn/problems/sort-an-array/
 * @version 1.0
 * @date 2022/7/18 20:06 学习多种排序算法，二刷，面试题
 */
public class sortArray {

  public static void main(String[] args) {
    int[] nums = {1, 3, 2, 5, 4};
    sortArray(nums);
    for (int num : nums) {
      System.out.println(num);
    }
  }

  // 冒泡排序：进行 n-1 轮排序，每一轮都把最大的数值放到后面去
  // 时间复杂度O(n^2)
  static int[] sortArray(int[] nums) {
    // 遍历数组的轮数 nums.length - 1
    for (int i = 0; i < nums.length - 1; i++) {
      // 遍历数组时，从头遍历，但是之前放到后面的较大数，不用再比较（即使继续比较一次，只是浪费时间，不会影响结果）
      for (int j = 0; j < nums.length - 1 - i; j++) {
        // 每次比较当前元素和下一个元素，最后一个元素和倒数第二个元素比较，所以 j < nums.length - 1
        // 当前元素大于下一个元素，交换位置
        if (nums[j] > nums[j + 1]) {
          int temp = nums[j];
          nums[j] = nums[j + 1];
          nums[j + 1] = temp;
        }
      }
    }
    return nums;
  }

  /**
   * 快速排序：选取一个 pivot ，比pivot小的数放在左边，比pivot大的数字放在右边
   * 不推荐理由：写得过于复杂，请看 leetcode.array.sortArray1
   * @author Cheng Jun
   * @date 2022/7/24 20:54
   * @param nums
   * @return int[]
   * @see sortArray1
   */
  @Deprecated
  static int[] sortArray1(int[] nums) {
    randomizedQuicksort(nums, 0, nums.length - 1);
    return nums;
  }

  static void randomizedQuicksort(int[] nums, int left, int right) {
    if (left < right) {
      int pos = randomizedPartition(nums, left, right);
      randomizedQuicksort(nums, left, pos - 1);
      randomizedQuicksort(nums, pos + 1, right);
    }
  }

  static int randomizedPartition(int[] nums, int left, int right) {
    int i = new Random().nextInt(right - left + 1) + left; // 随机选一个作为我们的主元
    swap(nums, right, i);
    return partition(nums, left, right);
  }

  static int partition(int[] nums, int left, int right) {
    // int pivot = nums[right];
    // int i = left - 1;
    // for (int j = left; j < right; j++) {
    //     if (nums[j] <= pivot) {
    //         i = i + 1;
    //         swap(nums, i, j);
    //     }
    // }
    // swap(nums, i + 1, right);
    // return i + 1;
    int pivot = nums[right];
    int lessPivotCount = 0;
    for (int i = left; i < right; i++) {
      if (nums[i] <= pivot) {
        swap(nums, left + lessPivotCount, i);
        lessPivotCount++;
      }
    }
    swap(nums, left + lessPivotCount, right);
    return left + lessPivotCount;
  }

  static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}
